<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 BASIC interpreter
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora057.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora059.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> BASIC interpreter</H2>
<A NAME="sec-basic"></A>
The application described in this section is a program interpreter for
Basic. Thus, it is a program that can run other programs written in
Basic. Of course, we will only deal with a restricted language,
which contains the following commands:<BR>
<BR>
<UL>
<LI>
 <B>PRINT</B> <I>expression</I> <BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=center NOWRAP>&nbsp;&nbsp;</TD>
<TD  ALIGN=left NOWRAP>Prints the result of the evaluation of the expression.</TD>
</TR></TABLE><BR>

<LI> <B>INPUT</B> <I>variable</I> <BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=center NOWRAP>&nbsp;&nbsp;</TD>
<TD  ALIGN=left NOWRAP>
 Prints a <I>prompt</I> (<TT>?</TT>), reads an integer typed in by the
user, and assigns its value to the variable.</TD>
</TR></TABLE><BR>

<LI> <B>LET</B> <I>variable</I> <B>=</B> <I>expression</I> <BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=center NOWRAP>&nbsp;&nbsp;</TD>
<TD  ALIGN=left NOWRAP>Assigns the result of the evaluation of <I>expression</I> to the variable.</TD>
</TR></TABLE><BR>

<LI> <B>GOTO</B> <I>line number</I><BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=center NOWRAP>&nbsp;&nbsp;</TD>
<TD  ALIGN=left NOWRAP>Continues execution at the given line.</TD>
</TR></TABLE><BR>

<LI> <B>IF</B> <I>condition</I> <B>THEN</B> <I>line number</I> <BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=center NOWRAP>&nbsp;&nbsp;</TD>
<TD  ALIGN=left NOWRAP>
Continues execution at the given line if the <EM>condition</EM> is true.</TD>
</TR></TABLE><BR>

<LI> <B>REM</B> <I>any string</I> <BR>
<BR>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=center NOWRAP>&nbsp;&nbsp;</TD>
<TD  ALIGN=left NOWRAP>One-line comment.</TD>
</TR></TABLE></UL>Every line of a Basic program is labelled with a line number, and
contains only one command. For instance, a program that computes and
then prints the factorial of an integer given by the user is written:
<PRE> 
 5  REM inputting the argument
10  PRINT " factorial of:"
20  INPUT A
30  LET B = 1 
35  REM beginning of the loop
40  IF A &lt;= 1 THEN 80 
50  LET B = B * A
60  LET A = A - 1
70  GOTO 40 
75  REM prints the result
80  PRINT B
</PRE>We also wish to write a small text editor, working as a toplevel interactive
loop. It should be able to add new lines, display a program, execute
it, and display the result.
Execution of the program is started with the
<TT>RUN</TT> command. Here is an example of the evaluation of this
program:
<PRE>
&gt; RUN
 factorial of: ? 5
120
</PRE>The interpreter is implemented in several distinct parts:
<DL COMPACT=compact>
<DT>Description of the abstract syntax<DD>: describes the definition of data
types to represent Basic programs, as well as their components
(lines, commands, expressions, etc.).<BR>
<BR>

<DT>Program pretty printing<DD>: consists of transforming the
internal representation of Basic programs to strings, in order
to display them.<BR>
<BR>

<DT>Lexing and parsing<DD>: accomplish the inverse 
transformation, that is, transform a string into the internal
representation of a Basic program (the abstract syntax).<BR>
<BR>

<DT>Evaluation<DD>: is the heart of the interpreter. It controls
and runs the program. As we will see, functional languages, such as
Objective CAML, are particularly well adapted for this kind of problem.<BR>
<BR>

<DT>Toplevel interactive loop<DD>: glues together all the previous parts.
</DL><A NAME="toc79"></A>
<H3> Abstract syntax</H3>
<A NAME="subsec-gram-basic"></A>
Figure&nbsp;<A HREF="book-ora058.html#fig-gram-basic">6.2</A> introduces the concrete syntax, as a BNF
grammar, of the Basic we will implement. This kind of description
for language syntaxes is described in chapter&nbsp;<A HREF="index.html#chap-AlexS">11</A>,
page&nbsp;<A HREF="book-ora106.html#sec-BNF">??</A>.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<TABLE CELLSPACING=2 CELLPADDING=0>
<TR><TD  ALIGN=right NOWRAP><FONT COLOR=navy>Unary_Op</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP>- &nbsp;&nbsp; | &nbsp;&nbsp; !</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP><FONT COLOR=navy>Binary_Op</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP>+ &nbsp;&nbsp; | &nbsp;&nbsp; - &nbsp;&nbsp; | &nbsp;&nbsp; * &nbsp;&nbsp; | &nbsp;&nbsp; / &nbsp;&nbsp; |
 &nbsp;&nbsp; %</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP>= &nbsp;&nbsp; | &nbsp;&nbsp; &lt; &nbsp;&nbsp; | &nbsp;&nbsp; &gt; &nbsp;&nbsp; | &nbsp;&nbsp; &lt;= &nbsp;&nbsp; |
 &nbsp;&nbsp; &gt;= &nbsp;&nbsp; | &nbsp;&nbsp; &lt;&gt;</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP>&amp; &nbsp;&nbsp; | &nbsp;&nbsp; '&nbsp;|&nbsp;'</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP><FONT COLOR=navy>Expression</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><EM>integer</EM></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><EM>variable</EM></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><TT>"string"</TT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Unary_Op</FONT> &nbsp;&nbsp;<FONT COLOR=navy>Expression</FONT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Expression</FONT> &nbsp;&nbsp;<FONT COLOR=navy>Binary_Op</FONT> &nbsp;&nbsp;<FONT COLOR=navy>Expression</FONT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP>(  <FONT COLOR=navy>Expression</FONT>   )</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP><FONT COLOR=navy>Command</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><B>REM</B>  <EM>string</EM></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><B>GOTO</B>  <EM>integer</EM></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><B>LET</B>  <EM>variable</EM>  =  <FONT COLOR=navy>Expression</FONT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><B>PRINT</B>  <FONT COLOR=navy>Expression</FONT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><B>INPUT</B>  <EM>variable</EM></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><B>IF</B>  <FONT COLOR=navy>Expression</FONT>  <B>THEN</B>  <EM>integer</EM></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP><FONT COLOR=navy>Line</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><EM>integer</EM> <FONT COLOR=navy>Command</FONT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP><FONT COLOR=navy>Program</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Line</FONT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
<TD  ALIGN=center NOWRAP>|</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Line</FONT> <FONT COLOR=navy>Program</FONT></TD>
</TR>
<TR><TD  ALIGN=right NOWRAP>&nbsp;</TD>
</TR>
<TR><TD  ALIGN=right NOWRAP><FONT COLOR=navy>Phrase</FONT></TD>
<TD  ALIGN=center NOWRAP>::=</TD>
<TD  ALIGN=left NOWRAP><FONT COLOR=navy>Line</FONT> | <B>RUN</B> | <B>LIST</B> | <B>END</B></TD>
</TR></TABLE>
</DIV>
<BR>
<DIV ALIGN=center>Figure 6.2: BASIC Grammar.</DIV><BR>

<A NAME="fig-gram-basic"></A>
<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>We can see that the way expressions are defined does not ensure that a
well formed expression can be evaluated. For instance, <TT>1+"hello"</TT> is an expression, and yet it is not possible to evaluate
it. This deliberate choice lets us simplify both the abstract syntax 
and the parsing of the Basic language. The price to pay for
this choice is that a syntactically correct Basic program may generate
a runtime error because of a type mismatch.<BR>
<BR>
Defining Objective CAML data types for this abstract syntax is easy,
we simply translate the concrete syntax into a sum type:


<PRE><BR># <B>type</B><CODE> </CODE>unr_op<CODE> </CODE><CODE>=</CODE><CODE> </CODE>UMINUS<CODE> </CODE><CODE>|</CODE><CODE> </CODE>NOT<CODE> </CODE><CODE> </CODE>;;<BR># <B>type</B><CODE> </CODE>bin_op<CODE> </CODE><CODE>=</CODE><CODE> </CODE>PLUS<CODE> </CODE><CODE>|</CODE><CODE> </CODE>MINUS<CODE> </CODE><CODE>|</CODE><CODE> </CODE>MULT<CODE> </CODE><CODE>|</CODE><CODE> </CODE>DIV<CODE> </CODE><CODE>|</CODE><CODE> </CODE>MOD<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>EQUAL<CODE> </CODE><CODE>|</CODE><CODE> </CODE>LESS<CODE> </CODE><CODE>|</CODE><CODE> </CODE>LESSEQ<CODE> </CODE><CODE>|</CODE><CODE> </CODE>GREAT<CODE> </CODE><CODE>|</CODE><CODE> </CODE>GREATEQ<CODE> </CODE><CODE>|</CODE><CODE> </CODE>DIFF<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>AND<CODE> </CODE><CODE>|</CODE><CODE> </CODE>OR<CODE> </CODE><CODE> </CODE>;;<BR># <B>type</B><CODE> </CODE>expression<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ExpInt<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpVar<CODE> </CODE><B>of</B><CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpStr<CODE> </CODE><B>of</B><CODE> </CODE>string<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpUnr<CODE> </CODE><B>of</B><CODE> </CODE>unr_op<CODE> </CODE><CODE>*</CODE><CODE> </CODE>expression<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpBin<CODE> </CODE><B>of</B><CODE> </CODE>expression<CODE> </CODE><CODE>*</CODE><CODE> </CODE>bin_op<CODE> </CODE><CODE>*</CODE><CODE> </CODE>expression<CODE> </CODE><CODE> </CODE>;;<BR># <B>type</B><CODE> </CODE>command<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Rem<CODE> </CODE><B>of</B><CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Goto<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Print<CODE> </CODE><B>of</B><CODE> </CODE>expression<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Input<CODE> </CODE><B>of</B><CODE> </CODE>string<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>If<CODE> </CODE><B>of</B><CODE> </CODE>expression<CODE> </CODE><CODE>*</CODE><CODE> </CODE>int<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Let<CODE> </CODE><B>of</B><CODE> </CODE>string<CODE> </CODE><CODE>*</CODE><CODE> </CODE>expression<CODE> </CODE><CODE> </CODE>;;<BR># <B>type</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>num<CODE> </CODE><CODE>:</CODE><CODE> </CODE>int<CODE> </CODE>;<CODE> </CODE>cmd<CODE> </CODE><CODE>:</CODE><CODE> </CODE>command<CODE> </CODE>}<CODE> </CODE><CODE> </CODE>;;<BR># <B>type</B><CODE> </CODE>program<CODE> </CODE><CODE>=</CODE><CODE> </CODE>line<CODE> </CODE>list<CODE> </CODE><CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
We also define the abstract syntax for the commands for the small
program editor:


<PRE><BR># <B>type</B><CODE> </CODE>phrase<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE> </CODE>Line<CODE> </CODE><B>of</B><CODE> </CODE>line<CODE> </CODE><CODE>|</CODE><CODE> </CODE>List<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Run<CODE> </CODE><CODE>|</CODE><CODE> </CODE>PEnd<CODE> </CODE><CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
It is convenient to allow the programmer to skip some parentheses in
arithmetic expressions. For instance, the expression 1+3*4 is
usually interpreted as 1+(3*4). To this end, we associate an integer
with each operator of the language:


<PRE><BR># <B>let</B><CODE> </CODE>priority_uop<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>NOT<CODE> </CODE>-&gt;<CODE> </CODE><CODE>1</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>UMINUS<CODE> </CODE>-&gt;<CODE> </CODE><CODE>7</CODE><BR><CODE> </CODE><B>let</B><CODE> </CODE>priority_binop<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>MULT<CODE> </CODE><CODE>|</CODE><CODE> </CODE>DIV<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>6</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>PLUS<CODE> </CODE><CODE>|</CODE><CODE> </CODE>MINUS<CODE> </CODE>-&gt;<CODE> </CODE><CODE>5</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>MOD<CODE> </CODE>-&gt;<CODE> </CODE><CODE>4</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>EQUAL<CODE> </CODE><CODE>|</CODE><CODE> </CODE>LESS<CODE> </CODE><CODE>|</CODE><CODE> </CODE>LESSEQ<CODE> </CODE><CODE>|</CODE><CODE> </CODE>GREAT<CODE> </CODE><CODE>|</CODE><CODE> </CODE>GREATEQ<CODE> </CODE><CODE>|</CODE><CODE> </CODE>DIFF<CODE> </CODE>-&gt;<CODE> </CODE><CODE>3</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>AND<CODE> </CODE><CODE>|</CODE><CODE> </CODE>OR<CODE> </CODE>-&gt;<CODE> </CODE><CODE>2</CODE><CODE> </CODE>;;<BR><CODE>val priority_uop : unr_op -&gt; int = &lt;fun&gt;</CODE><BR><CODE>val priority_binop : bin_op -&gt; int = &lt;fun&gt;</CODE><BR>

</PRE>

These integers indicate the priority of the operators. They
will be used to print and parse programs. <BR>
<BR>
<A NAME="toc80"></A>
<H3> Program pretty printing</H3>
To print a program, one needs to be able to convert abstract syntax
program lines into strings.<BR>
<BR>
Converting operators is easy:


<PRE><BR># <B>let</B><CODE> </CODE>pp_binop<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>PLUS<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"+"</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>MULT<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"*"</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>MOD<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>"%"</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>MINUS<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"-"</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>DIV<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"/"</CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>EQUAL<CODE> </CODE>-&gt;<CODE> </CODE><CODE>" = "</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>LESS<CODE> </CODE>-&gt;<CODE> </CODE><CODE>" &lt; "</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>LESSEQ<CODE> </CODE>-&gt;<CODE> </CODE><CODE>" &lt;= "</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>GREAT<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>" &gt; "</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>GREATEQ<CODE> </CODE>-&gt;<CODE> </CODE><CODE>" &gt;= "</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>DIFF<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>" &lt;&gt; "</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>AND<CODE> </CODE>-&gt;<CODE> </CODE><CODE>" &amp; "</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>OR<CODE> </CODE>-&gt;<CODE> </CODE><CODE>" | "</CODE><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><B>let</B><CODE> </CODE>pp_unrop<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE>UMINUS<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"-"</CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>NOT<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"!"</CODE><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val pp_binop : bin_op -&gt; string = &lt;fun&gt;</CODE><BR><CODE>val pp_unrop : unr_op -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>

Expression printing needs to take into account operator priority to
print as few parentheses as possible. For instance, parentheses are
put around a subexpression at the right of an operator only if the
subexpression's main operator has a lower priority that the main
operator of the whole expression. Also, arithmetic operators are
left-associative, thus the expression 1-2-3 is interpreted as
(1-2)-3.<BR>
<BR>
To deal with this, we use two auxiliary functions <TT>ppl</TT> and
<TT>ppr</TT> to print left and right subtrees, respectively. These
functions take two arguments: the tree to print and the priority of
the enclosing operator, which is used to decide if parentheses are 
necessary. Left
and right subtrees are distinguished to deal with associativity. If
the current operator priority is the same than the enclosing operator
priority, left trees do not need parentheses whereas right ones may
require them, as in 1-(2-3) or 1-(2+3).<BR>
<BR>
The initial tree is taken as a left subtree with minimal priority
(0).
The expression pretty printing function <TT>pp_expression</TT> is:


<PRE><BR># <B>let</B><CODE> </CODE>parenthesis<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>"("</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE>x<CODE> </CODE><CODE>^</CODE><CODE> </CODE><CODE>")"</CODE>;;<CODE> </CODE><CODE> </CODE><BR><CODE>val parenthesis : string -&gt; string = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>pp_expression<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>ppl<CODE> </CODE>pr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ExpInt<CODE> </CODE>n<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>n<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpVar<CODE> </CODE>v<CODE> </CODE>-&gt;<CODE> </CODE>v<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpStr<CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE><CODE>"\""</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE>s<CODE> </CODE><CODE>^</CODE><CODE> </CODE><CODE>"\""</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpUnr<CODE> </CODE><TT>(</TT>op<CODE>,</CODE>e<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>res<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>pp_unrop<CODE> </CODE>op<TT>)</TT><CODE>^</CODE><TT>(</TT>ppl<CODE> </CODE><TT>(</TT>priority_uop<CODE> </CODE>op<TT>)</TT><CODE> </CODE>e<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>if</B><CODE> </CODE>pr<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>then</B><CODE> </CODE>res<CODE> </CODE><B>else</B><CODE> </CODE>parenthesis<CODE> </CODE>res<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpBin<CODE> </CODE><TT>(</TT>e1<CODE>,</CODE>op<CODE>,</CODE>e2<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>pr2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>priority_binop<CODE> </CODE>op<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>let</B><CODE> </CODE>res<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>ppl<CODE> </CODE>pr2<CODE> </CODE>e1<TT>)</TT><CODE>^</CODE><TT>(</TT>pp_binop<CODE> </CODE>op<TT>)</TT><CODE>^</CODE><TT>(</TT>ppr<CODE> </CODE>pr2<CODE> </CODE>e2<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(* parenthesis if priority is not greater *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>if</B><CODE> </CODE>pr2<CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>pr<CODE> </CODE><B>then</B><CODE> </CODE>res<CODE> </CODE><B>else</B><CODE> </CODE>parenthesis<CODE> </CODE>res<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>and</B><CODE> </CODE>ppr<CODE> </CODE>pr<CODE> </CODE>exp<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>exp<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(*  right subtrees only differ for binary operators *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ExpBin<CODE> </CODE><TT>(</TT>e1<CODE>,</CODE>op<CODE>,</CODE>e2<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>pr2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>priority_binop<CODE> </CODE>op<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>let</B><CODE> </CODE>res<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>ppl<CODE> </CODE>pr2<CODE> </CODE>e1<TT>)</TT><CODE>^</CODE><TT>(</TT>pp_binop<CODE> </CODE>op<TT>)</TT><CODE>^</CODE><TT>(</TT>ppr<CODE> </CODE>pr2<CODE> </CODE>e2<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>if</B><CODE> </CODE>pr2<CODE> </CODE><CODE>&gt;</CODE><CODE> </CODE>pr<CODE> </CODE><B>then</B><CODE> </CODE>res<CODE> </CODE><B>else</B><CODE> </CODE>parenthesis<CODE> </CODE>res<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>ppl<CODE> </CODE>pr<CODE> </CODE>exp<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>ppl<CODE> </CODE><CODE>0</CODE><CODE> </CODE>;;<BR><CODE>val pp_expression : expression -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Command pretty printing uses the expression pretty printing
function. Printing a line consists of printing the line number before
the command.


<PRE><BR># <B>let</B><CODE> </CODE>pp_command<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Rem<CODE> </CODE>s<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><CODE>"REM "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE>s<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Goto<CODE> </CODE>n<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><CODE>"GOTO "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>n<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Print<CODE> </CODE>e<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><CODE>"PRINT "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>pp_expression<CODE> </CODE>e<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Input<CODE> </CODE>v<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><CODE>"INPUT "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE>v<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>If<CODE> </CODE><TT>(</TT>e<CODE>,</CODE>n<TT>)</TT><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><CODE>"IF "</CODE><CODE>^</CODE><TT>(</TT>pp_expression<CODE> </CODE>e<TT>)</TT><CODE>^</CODE><CODE>" THEN "</CODE><CODE>^</CODE><TT>(</TT>string_of_int<CODE> </CODE>n<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Let<CODE> </CODE><TT>(</TT>v<CODE>,</CODE>e<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><CODE>"LET "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE>v<CODE> </CODE><CODE>^</CODE><CODE> </CODE><CODE>" = "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>pp_expression<CODE> </CODE>e<TT>)</TT><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val pp_command : command -&gt; string = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>pp_line<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>string_of_int<CODE> </CODE>l<CODE>.</CODE>num<TT>)</TT><CODE> </CODE><CODE>^</CODE><CODE> </CODE><CODE>"  "</CODE><CODE> </CODE><CODE>^</CODE><CODE> </CODE><TT>(</TT>pp_command<CODE> </CODE>l<CODE>.</CODE>cmd<TT>)</TT><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val pp_line : line -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc81"></A>
<H3> Lexing</H3><A NAME="basic-lex0"></A>Lexing and parsing do the inverse transformation of
printing, going from a string to a syntax tree. Lexing
splits the text of a command line into independent lexical units
called lexemes, with Objective CAML type:


<PRE><BR># <B>type</B><CODE> </CODE>lexeme<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Lint<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lident<CODE> </CODE><B>of</B><CODE> </CODE>string<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lsymbol<CODE> </CODE><B>of</B><CODE> </CODE>string<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lstring<CODE> </CODE><B>of</B><CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lend<CODE> </CODE>;;<BR>

</PRE>

A particular lexeme denotes the end of an expression: <TT>Lend</TT>.
It is not present in the text of the expression, but is created by the
lexing function (see the <TT>lexer</TT> function, page
<A HREF="book-ora058.html#fun-lexer">??</A>).<BR>
<BR>
The string being lexed is kept in a record that contains a mutable
field indicating the position after which lexing has not been
done yet. Since the size of the string is used several times and does
not change, it is also stored in the record:


<PRE><BR># <B>type</B><CODE> </CODE>string_lexer<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{string<CODE>:</CODE>string;<CODE> </CODE><B>mutable</B><CODE> </CODE>current<CODE>:</CODE>int;<CODE> </CODE>size<CODE>:</CODE>int<CODE> </CODE>}<CODE> </CODE>;;<BR>

</PRE>

This representation lets us define the lexing of a string as the
application of a function to a value of type <I>string_lexer</I>
returning a value of type <I>lexeme</I>. Modifying the current
position in the string is done as a side effect.<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>init_lex<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>string<CODE>=</CODE>s;<CODE> </CODE>current<CODE>=</CODE><CODE>0</CODE><CODE> </CODE>;<CODE> </CODE>size<CODE>=</CODE>String.length<CODE> </CODE>s<CODE> </CODE>}<CODE> </CODE>;;<BR><CODE>val init_lex : string -&gt; string_lexer = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>forward<CODE> </CODE>cl<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cl<CODE>.</CODE>current<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>cl<CODE>.</CODE>current<CODE>+</CODE><CODE>1</CODE><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val forward : string_lexer -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>forward_n<CODE> </CODE>cl<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cl<CODE>.</CODE>current<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>cl<CODE>.</CODE>current<CODE>+</CODE>n<CODE> </CODE>;;<BR><CODE>val forward_n : string_lexer -&gt; int -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>extract<CODE> </CODE>pred<CODE> </CODE>cl<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>st<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cl<CODE>.</CODE>string<CODE> </CODE><B>and</B><CODE> </CODE>pos<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cl<CODE>.</CODE>current<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>ext<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE>&lt;</CODE>cl<CODE>.</CODE>size<CODE> </CODE><CODE>&amp;&amp;</CODE><CODE> </CODE><TT>(</TT>pred<CODE> </CODE>st<CODE>.[</CODE>n<CODE>]</CODE><TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE>ext<CODE> </CODE><TT>(</TT>n<CODE>+</CODE><CODE>1</CODE><TT>)</TT><CODE> </CODE><B>else</B><CODE> </CODE>n<CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>res<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ext<CODE> </CODE>pos<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>cl<CODE>.</CODE>current<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>res<CODE> </CODE>;<CODE> </CODE>String.sub<CODE> </CODE>cl<CODE>.</CODE>string<CODE> </CODE>pos<CODE> </CODE><TT>(</TT>res<CODE>-</CODE>pos<TT>)</TT><CODE> </CODE><CODE> </CODE>;;<BR><CODE>val extract : (char -&gt; bool) -&gt; string_lexer -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The following functions extract a lexeme from the string and modify
the current position. The two functions <TT>extract_int</TT> and
<TT>extract_ident</TT> extract an integer and an identifier,
respectively.


<PRE><BR># <B>let</B><CODE> </CODE>extract_int<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>is_int<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><CODE>'0'</CODE><CODE>..</CODE><CODE>'9'</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>function</B><CODE> </CODE>cl<CODE> </CODE>-&gt;<CODE> </CODE>int_of_string<CODE> </CODE><TT>(</TT>extract<CODE> </CODE>is_int<CODE> </CODE>cl<TT>)</TT><BR><CODE> </CODE><B>let</B><CODE> </CODE>extract_ident<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>is_alpha_num<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>'a'</CODE><CODE>..</CODE><CODE>'z'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'A'</CODE><CODE>..</CODE><CODE>'Z'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'0'</CODE><CODE> </CODE><CODE>..</CODE><CODE> </CODE><CODE>'9'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'_'</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>false</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>extract<CODE> </CODE>is_alpha_num<CODE> </CODE>;;<BR><CODE>val extract_int : string_lexer -&gt; int = &lt;fun&gt;</CODE><BR><CODE>val extract_ident : string_lexer -&gt; string = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The <TT>lexer</TT> function uses the two previous functions to extract
a lexeme.


<PRE><BR># <B>exception</B><CODE> </CODE>LexerError<CODE> </CODE>;;<BR><CODE>exception LexerError</CODE><BR># <B>let</B><CODE> </CODE><CODE> </CODE><B>rec</B><CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>lexer_char<CODE> </CODE>c<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>c<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>' '</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'\t'</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>forward<CODE> </CODE>cl<CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'a'</CODE><CODE>..</CODE><CODE>'z'</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'A'</CODE><CODE>..</CODE><CODE>'Z'</CODE><CODE> </CODE>-&gt;<CODE> </CODE>Lident<CODE> </CODE><TT>(</TT>extract_ident<CODE> </CODE>cl<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'0'</CODE><CODE>..</CODE><CODE>'9'</CODE><CODE> </CODE>-&gt;<CODE> </CODE>Lint<CODE> </CODE><TT>(</TT>extract_int<CODE> </CODE>cl<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'"'</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>forward<CODE> </CODE>cl<CODE> </CODE>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>res<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Lstring<CODE> </CODE><TT>(</TT>extract<CODE> </CODE><TT>(</TT><TT>(</TT><CODE>&lt;&gt;</CODE><TT>)</TT><CODE> </CODE><CODE>'"'</CODE><TT>)</TT><CODE> </CODE>cl<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>forward<CODE> </CODE>cl<CODE> </CODE>;<CODE> </CODE>res<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'+'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'-'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'*'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'/'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'%'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'&amp;'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'|'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'!'</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'='</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'('</CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>')'</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>forward<CODE> </CODE>cl;<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>String.make<CODE> </CODE><CODE>1</CODE><CODE> </CODE>c<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'&lt;'</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'&gt;'</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>forward<CODE> </CODE>cl;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>cl<CODE>.</CODE>current<CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>cl<CODE>.</CODE>size<CODE> </CODE><B>then</B><CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>String.make<CODE> </CODE><CODE>1</CODE><CODE> </CODE>c<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>cs<CODE> </CODE><CODE>=</CODE><CODE> </CODE>cl<CODE>.</CODE>string<CODE>.[</CODE>cl<CODE>.</CODE>current<CODE>]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><TT>(</TT><CODE> </CODE><B>match</B><CODE> </CODE><TT>(</TT>c<CODE>,</CODE>cs<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><CODE>'&lt;'</CODE><CODE>,</CODE><CODE>'='</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>forward<CODE> </CODE>cl;<CODE> </CODE>Lsymbol<CODE> </CODE><CODE>"&lt;="</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><CODE>'&gt;'</CODE><CODE>,</CODE><CODE>'='</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>forward<CODE> </CODE>cl;<CODE> </CODE>Lsymbol<CODE> </CODE><CODE>"&gt;="</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT><CODE>'&lt;'</CODE><CODE>,</CODE><CODE>'&gt;'</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>forward<CODE> </CODE>cl;<CODE> </CODE>Lsymbol<CODE> </CODE><CODE>"&lt;&gt;"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>String.make<CODE> </CODE><CODE>1</CODE><CODE> </CODE>c<TT>)</TT><CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>LexerError<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>cl<CODE>.</CODE>current<CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>cl<CODE>.</CODE>size<CODE> </CODE><B>then</B><CODE> </CODE>Lend<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>lexer_char<CODE> </CODE>cl<CODE>.</CODE>string<CODE>.[</CODE>cl<CODE>.</CODE>current<CODE>]</CODE><CODE> </CODE>;;<BR><CODE>val lexer : string_lexer -&gt; lexeme = &lt;fun&gt;</CODE><BR>

</PRE>
<A NAME="fun-lexer"></A><BR>
<BR>
The <TT>lexer</TT> function is very simple: it matches the current
character of a string and, based on its value, extracts the
corresponding lexeme and modifies the current position to the start of
the next lexeme. The code is simple because, for all characters except
two, the current character defines which lexeme to extract. In the
more complicated cases of <CODE>'&lt;'</CODE>, we need to look at the next
character, which might be a <CODE>'='</CODE> or a <CODE>'&gt;'</CODE>, producing two different
lexemes. The same problem arises with <CODE>'&gt;'</CODE>.<BR>
<BR>
<A NAME="toc82"></A>
<H3> Parsing</H3><A NAME="basic-synt0"></A>
The only difficulty in parsing our language comes from expressions.
Indeed, knowing the beginning of an expression is not enough to know
its structure. For instance, having parsed the beginning of an
expression as being 1+2+3, the resulting syntax tree for this part
depends on the rest of the expression: its structure is different when
it is followed by +4 or *4 (see figure <A HREF="book-ora058.html#fig-basic-ex1">6.3</A>).
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora022.gif"> </DIV>
<BR>
<DIV ALIGN=center>Figure 6.3: Basic: abstract syntax tree examples<A NAME="fig-basic-ex1"></A>.</DIV><BR>

<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
However, since the tree structure for 1+2 is the same in both cases,
it can be built. As the position of +3 in the structure is not fully
known, it is temporarily stored.<BR>
<BR>
To build the abstract syntax tree, we use a pushdown automaton
similar to the one built by <EM>yacc</EM> (see page
<A HREF="book-ora106.html#sec-ocamlyacc">??</A>). Lexemes are read one by one and put
on a stack until there is enough information to build the
expression. They are then removed from the stack and replaced by the
expression. This latter operation is called reduction.<BR>
<BR>
The stack elements have type:


<PRE><BR># <B>type</B><CODE> </CODE>exp_elem<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Texp<CODE> </CODE><B>of</B><CODE> </CODE>expression<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(* expression       *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Tbin<CODE> </CODE><B>of</B><CODE> </CODE>bin_op<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(* binary operator  *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Tunr<CODE> </CODE><B>of</B><CODE> </CODE>unr_op<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(* unary operator   *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Tlp<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(* left parenthesis *)</CODE><CODE> </CODE>;;<BR>

</PRE>

Right parentheses are not stored on the stack as only left parentheses
matter for reduction.<BR>
<BR>
Figure <A HREF="book-ora058.html#fig-basic-ex2">6.4</A> illustrates the way the stack is used to
parse the expression (1+2*3)+4. The character above the arrow is the
current character of the string.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<IMG SRC="book-ora023.gif">
</DIV>
<BR>
<DIV ALIGN=center>Figure 6.4: Basic: abstract syntax tree construction
 example<A NAME="fig-basic-ex2"></A>.</DIV><BR>

<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>We define an exception for syntax errors.


<PRE><BR># <B>exception</B><CODE> </CODE>ParseError<CODE> </CODE>;;<BR>

</PRE>

The first step consists of transforming symbols into operators:


<PRE><BR># <B>let</B><CODE> </CODE>unr_symb<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"!"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>NOT<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"-"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>UMINUS<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><BR><CODE> </CODE><B>let</B><CODE> </CODE>bin_symb<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"+"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>PLUS<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"-"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>MINUS<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"*"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>MULT<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"/"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>DIV<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"%"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>MOD<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"="</CODE><CODE> </CODE>-&gt;<CODE> </CODE>EQUAL<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&lt;"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>LESS<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&lt;="</CODE><CODE> </CODE>-&gt;<CODE> </CODE>LESSEQ<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&gt;"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>GREAT<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&gt;="</CODE><CODE> </CODE>-&gt;<CODE> </CODE>GREATEQ<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&lt;&gt;"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>DIFF<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&amp;"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>AND<CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"|"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>OR<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><BR><CODE> </CODE><B>let</B><CODE> </CODE>tsymb<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>try</B><CODE> </CODE>Tbin<CODE> </CODE><TT>(</TT>bin_symb<CODE> </CODE>s<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE>ParseError<CODE> </CODE>-&gt;<CODE> </CODE>Tunr<CODE> </CODE><TT>(</TT>unr_symb<CODE> </CODE>s<TT>)</TT><CODE> </CODE>;;<BR><CODE>val unr_symb : string -&gt; unr_op = &lt;fun&gt;</CODE><BR><CODE>val bin_symb : string -&gt; bin_op = &lt;fun&gt;</CODE><BR><CODE>val tsymb : string -&gt; exp_elem = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The <TT>reduce</TT> function implements stack reduction. There are two
cases to consider, whether the stack starts with:
<UL>
<LI>
 
an expression followed by a unary operator,

<LI> 
an expression followed by a binary operator and an expression.
</UL>
Moreover, <TT>reduce</TT> takes an argument indicating the minimal
priority that an operator should have to trigger reduction. To avoid
this reduction condition, it suffices to give the minimal value, zero, 
as the priority.


<PRE><BR># <B>let</B><CODE> </CODE>reduce<CODE> </CODE>pr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE>e<TT>)</TT>::<TT>(</TT>Tunr<CODE> </CODE>op<TT>)</TT>::st<CODE> </CODE><CODE> </CODE><B>when</B><CODE> </CODE><CODE> </CODE><TT>(</TT>priority_uop<CODE> </CODE>op<TT>)</TT><CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>pr<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>Texp<CODE> </CODE><TT>(</TT>ExpUnr<CODE> </CODE><TT>(</TT>op<CODE>,</CODE>e<TT>)</TT><TT>)</TT><TT>)</TT>::st<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE>e1<TT>)</TT>::<TT>(</TT>Tbin<CODE> </CODE>op<TT>)</TT>::<TT>(</TT>Texp<CODE> </CODE>e2<TT>)</TT>::st<CODE> </CODE><CODE> </CODE><B>when</B><CODE> </CODE><CODE> </CODE><TT>(</TT>priority_binop<CODE> </CODE>op<TT>)</TT><CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>pr<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>Texp<CODE> </CODE><TT>(</TT>ExpBin<CODE> </CODE><TT>(</TT>e2<CODE>,</CODE>op<CODE>,</CODE>e1<TT>)</TT><TT>)</TT><TT>)</TT>::st<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE>;;<BR><CODE>val reduce : int -&gt; exp_elem list -&gt; exp_elem list = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Notice that expression elements are stacked as they are read. Thus it
is necessary to swap them when they are arguments of a binary
operator.<BR>
<BR>
The main function of our parser is <TT>stack_or_reduce</TT> that,
according to the lexeme given in argument, puts it on the stack or
triggers a reduction.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>stack_or_reduce<CODE> </CODE>lex<CODE> </CODE>stack<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>lex<CODE> </CODE><CODE>,</CODE><CODE> </CODE>stack<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Lint<CODE> </CODE>n<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE><TT>(</TT>ExpInt<CODE> </CODE>n<TT>)</TT><TT>)</TT>::stack<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lident<CODE> </CODE>v<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE><TT>(</TT>ExpVar<CODE> </CODE>v<TT>)</TT><TT>)</TT>::stack<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lstring<CODE> </CODE>s<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE><TT>(</TT>ExpStr<CODE> </CODE>s<TT>)</TT><TT>)</TT>::stack<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lsymbol<CODE> </CODE><CODE>"("</CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Tlp::stack<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lsymbol<CODE> </CODE><CODE>")"</CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE>e<TT>)</TT>::Tlp::st<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE>e<TT>)</TT>::st<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lsymbol<CODE> </CODE><CODE>")"</CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>stack_or_reduce<CODE> </CODE>lex<CODE> </CODE><TT>(</TT>reduce<CODE> </CODE><CODE>0</CODE><CODE> </CODE>stack<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lsymbol<CODE> </CODE>s<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>symbol<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>s<CODE>&lt;&gt;</CODE><CODE>"-"</CODE><CODE> </CODE><B>then</B><CODE> </CODE>tsymb<CODE> </CODE>s<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(* remove the ambiguity of the ``-'' symbol           *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>(* according to the last exp element put on the stack *)</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>match</B><CODE> </CODE>stack<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE><TT>(</TT>Texp<CODE> </CODE><CODE>_</CODE><TT>)</TT><CODE>::_</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Tbin<CODE> </CODE>MINUS<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Tunr<CODE> </CODE>UMINUS<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><TT>(</TT><CODE> </CODE><B>match</B><CODE> </CODE>symbol<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Tunr<CODE> </CODE>op<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><TT>(</TT>Tunr<CODE> </CODE>op<TT>)</TT>::stack<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Tbin<CODE> </CODE>op<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><CODE> </CODE><B>try</B><CODE> </CODE>stack_or_reduce<CODE> </CODE>lex<CODE> </CODE><TT>(</TT>reduce<CODE> </CODE><TT>(</TT>priority_binop<CODE> </CODE>op<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>stack<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>ParseError<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>Tbin<CODE> </CODE>op<TT>)</TT>::stack<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE>;;<BR><CODE>val stack_or_reduce : lexeme -&gt; exp_elem list -&gt; exp_elem list = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Once all lexemes are defined and stacked, the function
<TT>reduce_all</TT> builds the abstract syntax tree with the elements
remaining in the stack. If the expression being parsed is well formed,
only one element should remain in the stack, containing the tree for
this expression.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>reduce_all<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>function</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[</CODE>Texp<CODE> </CODE>x<CODE>]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>x<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>st<CODE> </CODE>-&gt;<CODE> </CODE>reduce_all<CODE> </CODE><TT>(</TT>reduce<CODE> </CODE><CODE>0</CODE><CODE> </CODE>st<TT>)</TT><CODE> </CODE>;;<BR><CODE>val reduce_all : exp_elem list -&gt; expression = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The <TT>parse_exp</TT> function is the main expression parsing
function. It reads a string, extracts its lexemes and passes them to the
<TT>stack_or_reduce</TT> function. Parsing stops when the current
lexeme satisfies a predicate that is given as an argument.


<PRE><BR># <B>let</B><CODE> </CODE>parse_exp<CODE> </CODE>stop<CODE> </CODE>cl<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE>ref<CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>parse_one<CODE> </CODE>stack<CODE> </CODE><CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT><CODE> </CODE>p<CODE>:=</CODE>cl<CODE>.</CODE>current<CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>cl<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>if</B><CODE> </CODE>not<CODE> </CODE><TT>(</TT>stop<CODE> </CODE>l<TT>)</TT><CODE> </CODE><B>then</B><CODE> </CODE>parse_one<CODE> </CODE><TT>(</TT>stack_or_reduce<CODE> </CODE>l<CODE> </CODE>stack<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT><CODE> </CODE>cl<CODE>.</CODE>current<CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE><CODE>!</CODE>p<CODE> </CODE>;<CODE> </CODE>reduce_all<CODE> </CODE>stack<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>parse_one<CODE> </CODE>[]<CODE> </CODE><CODE> </CODE>;;<BR><CODE>val parse_exp : (lexeme -&gt; bool) -&gt; string_lexer -&gt; expression = &lt;fun&gt;</CODE><BR>

</PRE>

Notice that the lexeme that made the parsing stop is not used to build
the expression. It is thus necessary to modify the current position to
its beginning (variable <TT>p</TT>) to parse it later.<BR>
<BR>
We can now parse a command line:


<PRE><BR># <B>let</B><CODE> </CODE>parse_cmd<CODE> </CODE>cl<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Lident<CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"REM"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>Rem<CODE> </CODE><TT>(</TT>extract<CODE> </CODE><TT>(</TT><B>fun</B><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>true</B><TT>)</TT><CODE> </CODE>cl<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"GOTO"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>Goto<CODE> </CODE><TT>(</TT><B>match</B><CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Lint<CODE> </CODE>p<CODE> </CODE>-&gt;<CODE> </CODE>p<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"INPUT"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>Input<CODE> </CODE><TT>(</TT><B>match</B><CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Lident<CODE> </CODE>v<CODE> </CODE>-&gt;<CODE> </CODE>v<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"PRINT"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>Print<CODE> </CODE><TT>(</TT>parse_exp<CODE> </CODE><TT>(</TT><TT>(</TT><CODE>=</CODE><TT>)</TT><CODE> </CODE>Lend<TT>)</TT><CODE> </CODE>cl<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"LET"</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>l2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><B>and</B><CODE> </CODE>l3<CODE> </CODE><CODE>=</CODE><CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><TT>(</TT><CODE> </CODE><B>match</B><CODE> </CODE>l2<CODE> </CODE><CODE>,</CODE>l3<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT>Lident<CODE> </CODE>v<CODE>,</CODE>Lsymbol<CODE> </CODE><CODE>"="</CODE><TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE>Let<CODE> </CODE><TT>(</TT>v<CODE>,</CODE>parse_exp<CODE> </CODE><TT>(</TT><TT>(</TT><CODE>=</CODE><TT>)</TT><CODE> </CODE>Lend<TT>)</TT><CODE> </CODE>cl<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"IF"</CODE><CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>test<CODE> </CODE><CODE>=</CODE><CODE> </CODE>parse_exp<CODE> </CODE><TT>(</TT><TT>(</TT><CODE>=</CODE><TT>)</TT><CODE> </CODE><TT>(</TT>Lident<CODE> </CODE><CODE>"THEN"</CODE><TT>)</TT><TT>)</TT><CODE> </CODE>cl<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><TT>(</TT><CODE> </CODE><B>match</B><CODE> </CODE>ignore<CODE> </CODE><TT>(</TT>lexer<CODE> </CODE>cl<TT>)</TT><CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Lint<CODE> </CODE>n<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>If<CODE> </CODE><TT>(</TT>test<CODE>,</CODE>n<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><CODE> </CODE>;;<BR><CODE>val parse_cmd : string_lexer -&gt; command = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
Finally, we implement the function to parse commands typed by the
user:
<A NAME="fun-basic-parse"></A>


<PRE><BR># <B>let</B><CODE> </CODE>parse<CODE> </CODE>str<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>cl<CODE> </CODE><CODE>=</CODE><CODE> </CODE>init_lex<CODE> </CODE>str<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>match</B><CODE> </CODE>lexer<CODE> </CODE>cl<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Lint<CODE> </CODE>n<CODE> </CODE>-&gt;<CODE> </CODE>Line<CODE> </CODE>{<CODE> </CODE>num<CODE>=</CODE>n<CODE> </CODE>;<CODE> </CODE>cmd<CODE>=</CODE>parse_cmd<CODE> </CODE>cl<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lident<CODE> </CODE><CODE>"LIST"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>List<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lident<CODE> </CODE><CODE>"RUN"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>Run<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Lident<CODE> </CODE><CODE>"END"</CODE><CODE> </CODE>-&gt;<CODE> </CODE>PEnd<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>ParseError<CODE> </CODE><CODE> </CODE>;;<BR><CODE>val parse : string -&gt; phrase = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc83"></A>
<H3> Evaluation</H3>
A Basic program is a list of lines. Execution starts at the first
line. Interpreting a program line consists of executing the task
corresponding to its command. There are three different kinds of
commands: input-output (<B>PRINT</B> and <B>INPUT</B>), variable
declaration or modification (<B>LET</B>), and flow control
(<B>GOTO</B> and <B>IF...THEN</B>). Input-output commands interact 
with the user and use the corresponding Objective CAML functions.<BR>
<BR>
Variable declaration and modification commands need to know how to
compute the value of an arithmetic expression and the memory
location to store the result. Expression evaluation returns an
integer, a boolean, or a string. Their type is <TT>value</TT>.


<PRE><BR># <B>type</B><CODE> </CODE>value<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Vint<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vstr<CODE> </CODE><B>of</B><CODE> </CODE>string<CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vbool<CODE> </CODE><B>of</B><CODE> </CODE>bool<CODE> </CODE><CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
Variable declaration should allocate some memory to store the
associated value. Similarly, variable modification requires the
modification of the associated value. Thus, evaluation of a Basic
program uses an <EM>environment</EM> that stores the association
between a variable name and its value. It is represented by an
association list of tuples (name,value):


<PRE>
<CODE> </CODE><BR># <B>type</B><CODE> </CODE>environment<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>string<CODE> </CODE><CODE>*</CODE><CODE> </CODE>value<TT>)</TT><CODE> </CODE>list<CODE> </CODE>;;<BR>

</PRE>

The variable name is used to access its value. Variable modification
modifies the association.<BR>
<BR>
Flow control commands, conditional or unconditional, specify the
number of the next line to execute. By default, it is the next
line. To do this, it is necessary to remember
the number of the current line.<BR>
<BR>
The list of commands representing the program being edited under
the toplevel is not an efficient data structure for running the
program. Indeed, it is then necessary to look at the whole list of
lines to find the line indicated by a flow control command
(<CODE>If</CODE> and <CODE>goto</CODE>). Replacing the list of lines with an array
of commands allows direct access to the command following a
flow control command, using the array index instead of the line
number in the flow control command. This solution requires some
preprocessing called assembly before executing a <TT>RUN</TT>
command. For reasons that will be detailed shortly, a program
after assembly is not represented as an array of commands but as an
array of lines:


<PRE><BR># <B>type</B><CODE> </CODE>code<CODE> </CODE><CODE>=</CODE><CODE> </CODE>line<CODE> </CODE>array<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
As in the calculator example of previous chapters, the interpreter
uses a state that is modified for each command evaluation. At each
step, we need to remember the whole program, the next line to
interpret and the values of the variables. The program being
interpreted is not exactly the one that was entered in the toplevel:
instead of a list of commands, it is an array of commands. Thus
the state of a program during execution is:


<PRE><BR># <B>type</B><CODE> </CODE>state_exec<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>line<CODE>:</CODE>int<CODE> </CODE>;<CODE> </CODE>xprog<CODE>:</CODE>code<CODE> </CODE>;<CODE> </CODE>xenv<CODE>:</CODE>environment<CODE> </CODE>}<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
Two different reasons may lead to an error during the evaluation of a
line: an error while computing an expression, or branching to an
absent line. They must be dealt with so that the interpreter exits
nicely, printing an error message. We define an exception as well as a
function to raise it, indicating the line where the error occurred.


<PRE><BR># <B>exception</B><CODE> </CODE>RunError<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE><BR><CODE> </CODE><B>let</B><CODE> </CODE>runerr<CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>raise<CODE> </CODE><TT>(</TT>RunError<CODE> </CODE>n<TT>)</TT><CODE> </CODE>;;<BR><CODE>exception RunError of int</CODE><BR><CODE>val runerr : int -&gt; 'a = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H5> Assembly</H5>
Assembling a program that is a list of numbered lines (type
<I>program</I>) consists of transforming this list into an array and
modifying the flow control commands. This last modification only
needs an association table between line numbers and array indexes.
This is easily provided by storing lines (with their line numbers),
instead of commands, in the array: to find the association between
a line number and the index in the array, we look the line number up
in the array and return the corresponding index. If no line is found
with this number, the index returned is <CODE>-</CODE><CODE>1</CODE>.


<PRE><BR># <B>exception</B><CODE> </CODE>Result_lookup_index<CODE> </CODE><B>of</B><CODE> </CODE>int<CODE> </CODE>;;<BR><CODE>exception Result_lookup_index of int</CODE><BR># <B>let</B><CODE> </CODE>lookup_index<CODE> </CODE>tprog<CODE> </CODE>num_line<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE><TT>(</TT>Array.length<CODE> </CODE>tprog<TT>)</TT><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>num_i<CODE> </CODE><CODE>=</CODE><CODE> </CODE>tprog<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE>num<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><B>if</B><CODE> </CODE>num_i<CODE>=</CODE>num_line<CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE><TT>(</TT>Result_lookup_index<CODE> </CODE>i<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>if</B><CODE> </CODE>num_i<CODE>&gt;</CODE>num_line<CODE> </CODE><B>then</B><CODE> </CODE>raise<CODE> </CODE><TT>(</TT>Result_lookup_index<CODE> </CODE><TT>(</TT><CODE>-</CODE><CODE>1</CODE><TT>)</TT><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>Result_lookup_index<CODE> </CODE>i<CODE> </CODE>-&gt;<CODE> </CODE>i<CODE> </CODE>;;<BR><CODE>val lookup_index : line array -&gt; int -&gt; int = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>assemble<CODE> </CODE>prog<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>tprog<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Array.of_list<CODE> </CODE>prog<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>for</B><CODE> </CODE>i<CODE>=</CODE><CODE>0</CODE><CODE> </CODE><B>to</B><CODE> </CODE><TT>(</TT>Array.length<CODE> </CODE>tprog<TT>)</TT><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>do</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>tprog<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE>.</CODE>cmd<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Goto<CODE> </CODE>n<CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>index<CODE> </CODE><CODE>=</CODE><CODE> </CODE>lookup_index<CODE> </CODE>tprog<CODE> </CODE>n<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>tprog<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>{<CODE> </CODE>tprog<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE>cmd<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Goto<CODE> </CODE>index<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>If<TT>(</TT>c<CODE>,</CODE>n<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>index<CODE> </CODE><CODE>=</CODE><CODE> </CODE>lookup_index<CODE> </CODE>tprog<CODE> </CODE>n<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>tprog<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><CODE>&lt;-</CODE><CODE> </CODE>{<CODE> </CODE>tprog<CODE>.</CODE><TT>(</TT>i<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE>cmd<CODE> </CODE><CODE>=</CODE><CODE> </CODE>If<CODE> </CODE><TT>(</TT>c<CODE>,</CODE>index<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>()<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>done</B><CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>tprog<CODE> </CODE>;;<BR><CODE>val assemble : line list -&gt; line array = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H5> Expression evaluation</H5>
<A NAME="sec-basic-evaluation"></A>
The evaluation function does a depth-first traversal on the abstract syntax
tree, and executes the operations indicated at each node.<BR>
<BR>
The <TT>RunError</TT> exception is raised in case of type
inconsistency, division by zero, or an undeclared variable.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>eval_exp<CODE> </CODE>n<CODE> </CODE>envt<CODE> </CODE>expr<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>expr<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>ExpInt<CODE> </CODE>p<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE>p<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpVar<CODE> </CODE>v<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT><CODE> </CODE><B>try</B><CODE> </CODE>List.assoc<CODE> </CODE>v<CODE> </CODE>envt<CODE> </CODE><B>with</B><CODE> </CODE>Not_found<CODE> </CODE>-&gt;<CODE> </CODE>runerr<CODE> </CODE>n<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpUnr<CODE> </CODE><TT>(</TT>UMINUS<CODE>,</CODE>e<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><CODE> </CODE><B>match</B><CODE> </CODE>eval_exp<CODE> </CODE>n<CODE> </CODE>envt<CODE> </CODE>e<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE>p<CODE> </CODE>-&gt;<CODE> </CODE>Vint<CODE> </CODE><TT>(</TT><CODE>-</CODE>p<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>runerr<CODE> </CODE>n<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpUnr<CODE> </CODE><TT>(</TT>NOT<CODE>,</CODE>e<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><TT>(</TT><CODE> </CODE><B>match</B><CODE> </CODE>eval_exp<CODE> </CODE>n<CODE> </CODE>envt<CODE> </CODE>e<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE>p<CODE> </CODE>-&gt;<CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>not<CODE> </CODE>p<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>runerr<CODE> </CODE>n<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpStr<CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE>Vstr<CODE> </CODE>s<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ExpBin<CODE> </CODE><TT>(</TT>e1<CODE>,</CODE>op<CODE>,</CODE>e2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>match</B><CODE> </CODE>eval_exp<CODE> </CODE>n<CODE> </CODE>envt<CODE> </CODE>e1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>op<CODE> </CODE><CODE>,</CODE><CODE> </CODE>eval_exp<CODE> </CODE>n<CODE> </CODE>envt<CODE> </CODE>e2<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>PLUS<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>+</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>MINUS<CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>-</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>MULT<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>*</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE> </CODE>DIV<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE><B>when</B><CODE> </CODE>v2<CODE>&lt;&gt;</CODE><CODE>0</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>/</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE> </CODE>MOD<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE><B>when</B><CODE> </CODE>v2<CODE>&lt;&gt;</CODE><CODE>0</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><B>mod</B><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>EQUAL<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>DIFF<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>&lt;&gt;</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE> </CODE>LESS<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE> </CODE>GREAT<CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>&gt;</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>LESSEQ<CODE> </CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>&lt;=</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vint<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>GREATEQ<CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vint<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>&gt;=</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vbool<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>AND<CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vbool<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>&amp;&amp;</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vbool<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>OR<CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vbool<CODE> </CODE>v2<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>||</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vstr<CODE> </CODE>v1<CODE> </CODE><CODE>,</CODE><CODE> </CODE>PLUS<CODE> </CODE><CODE>,</CODE><CODE> </CODE>Vstr<CODE> </CODE>v2<CODE> </CODE>-&gt;<CODE> </CODE>Vstr<CODE> </CODE><TT>(</TT>v1<CODE> </CODE><CODE>^</CODE><CODE> </CODE>v2<TT>)</TT><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE>,</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>runerr<CODE> </CODE>n<CODE> </CODE><CODE> </CODE>;;<BR><CODE>val eval_exp : int -&gt; (string * value) list -&gt; expression -&gt; value = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>

<H5> Command evaluation</H5>
To evaluate a command, we need a few additional functions.<BR>
<BR>
We add an association to an environment by removing a previous
association for the same variable name if there is one:


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>add<CODE> </CODE>v<CODE> </CODE>e<CODE> </CODE>env<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>env<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>[</CODE>v<CODE>,</CODE>e<CODE>]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><TT>(</TT>w<CODE>,</CODE>f<TT>)</TT>::l<CODE> </CODE>-&gt;<CODE> </CODE><B>if</B><CODE> </CODE>w<CODE>=</CODE>v<CODE> </CODE><B>then</B><CODE> </CODE><TT>(</TT>v<CODE>,</CODE>e<TT>)</TT>::l<CODE> </CODE><B>else</B><CODE> </CODE><TT>(</TT>w<CODE>,</CODE>f<TT>)</TT>::<TT>(</TT>add<CODE> </CODE>v<CODE> </CODE>e<CODE> </CODE>l<TT>)</TT><CODE> </CODE>;;<BR><CODE>val add : 'a -&gt; 'b -&gt; ('a * 'b) list -&gt; ('a * 'b) list = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
A function that prints the value of an integer or string is useful
for evaluation of the <CODE>PRINT</CODE> command.


<PRE><BR># <B>let</B><CODE> </CODE>print_value<CODE> </CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>v<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Vint<CODE> </CODE>n<CODE> </CODE>-&gt;<CODE> </CODE>print_int<CODE> </CODE>n<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vbool<CODE> </CODE><B>true</B><CODE> </CODE>-&gt;<CODE> </CODE>print_string<CODE> </CODE><CODE>"true"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vbool<CODE> </CODE><B>false</B><CODE> </CODE>-&gt;<CODE> </CODE>print_string<CODE> </CODE><CODE>"false"</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vstr<CODE> </CODE>s<CODE> </CODE>-&gt;<CODE> </CODE>print_string<CODE> </CODE>s<CODE> </CODE>;;<BR><CODE>val print_value : value -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The execution of a command corresponds to a transition from one
state to another. More precisely, the environment is modified if the
command is an assignment. Furthermore, the next line to execute is always
modified. As a convention, if the next line to execute does not exist, 
we set its value to <CODE>-</CODE><CODE>1</CODE>


<PRE><BR># <B>let</B><CODE> </CODE>next_line<CODE> </CODE>state<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>n<CODE> </CODE><CODE>=</CODE><CODE> </CODE>state<CODE>.</CODE>line<CODE>+</CODE><CODE>1</CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>n<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>Array.length<CODE> </CODE>state<CODE>.</CODE>xprog<CODE> </CODE><B>then</B><CODE> </CODE>n<CODE> </CODE><B>else</B><CODE> </CODE><CODE>-</CODE><CODE>1</CODE><CODE> </CODE>;;<BR><CODE>val next_line : state_exec -&gt; int = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE>eval_cmd<CODE> </CODE>state<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>state<CODE>.</CODE>xprog<CODE>.</CODE><TT>(</TT>state<CODE>.</CODE>line<TT>)</TT><CODE>.</CODE>cmd<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Rem<CODE> </CODE><CODE>_</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>next_line<CODE> </CODE>state<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Print<CODE> </CODE>e<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>print_value<CODE> </CODE><TT>(</TT>eval_exp<CODE> </CODE>state<CODE>.</CODE>line<CODE> </CODE>state<CODE>.</CODE>xenv<CODE> </CODE>e<TT>)</TT><CODE> </CODE>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_newline<CODE> </CODE>()<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>next_line<CODE> </CODE>state<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Let<TT>(</TT>v<CODE>,</CODE>e<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>ev<CODE> </CODE><CODE>=</CODE><CODE> </CODE>eval_exp<CODE> </CODE>state<CODE>.</CODE>line<CODE> </CODE>state<CODE>.</CODE>xenv<CODE> </CODE>e<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>next_line<CODE> </CODE>state<CODE> </CODE>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>xenv<CODE> </CODE><CODE>=</CODE><CODE> </CODE>add<CODE> </CODE>v<CODE> </CODE>ev<CODE> </CODE>state<CODE>.</CODE>xenv<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Goto<CODE> </CODE>n<CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>n<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Input<CODE> </CODE>v<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>try</B><CODE> </CODE>read_int<CODE> </CODE>()<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>Failure<CODE> </CODE><CODE>"int_of_string"</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>0</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>next_line<CODE> </CODE>state;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>xenv<CODE> </CODE><CODE>=</CODE><CODE> </CODE>add<CODE> </CODE>v<CODE> </CODE><TT>(</TT>Vint<CODE> </CODE>x<TT>)</TT><CODE> </CODE>state<CODE>.</CODE>xenv<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>If<CODE> </CODE><TT>(</TT>t<CODE>,</CODE>n<TT>)</TT><CODE> </CODE>-&gt;<CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>eval_exp<CODE> </CODE>state<CODE>.</CODE>line<CODE> </CODE>state<CODE>.</CODE>xenv<CODE> </CODE>t<CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Vbool<CODE> </CODE><B>true</B><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>n<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Vbool<CODE> </CODE><B>false</B><CODE> </CODE>-&gt;<CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE>next_line<CODE> </CODE>state<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>runerr<CODE> </CODE>state<CODE>.</CODE>line<CODE> </CODE><CODE> </CODE>;;<BR><CODE>val eval_cmd : state_exec -&gt; state_exec = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
On each call of the transition function <TT>eval_cmd</TT>, we
look up the current line, run it, then set the number of the next
line to run as the current line. If the last line of the program is
reached, the current line is given the value <EM>-1</EM>. This
will tell us when to stop.<BR>
<BR>

<H5> Program evaluation</H5>
We recursively apply the transition function until we reach a state
where the current line number is <CODE>-</CODE><CODE>1</CODE>.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>run<CODE> </CODE>state<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>state<CODE>.</CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>-</CODE><CODE>1</CODE><CODE> </CODE><B>then</B><CODE> </CODE>state<CODE> </CODE><B>else</B><CODE> </CODE>run<CODE> </CODE><TT>(</TT>eval_cmd<CODE> </CODE>state<TT>)</TT><CODE> </CODE>;;<BR><CODE>val run : state_exec -&gt; state_exec = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc84"></A>
<H3> Finishing touches</H3><A NAME="basic-meo"></A>
The only thing left to do is to write a small editor and to plug
together all the functions we wrote in the previous sections.<BR>
<BR>
The <TT>insert</TT> function adds a new line in the program at the
requested place.


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>insert<CODE> </CODE>line<CODE> </CODE>p<CODE> </CODE><CODE>=</CODE><CODE> </CODE><B>match</B><CODE> </CODE>p<CODE> </CODE><B>with</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>[]<CODE> </CODE>-&gt;<CODE> </CODE><CODE>[</CODE>line<CODE>]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>l::prog<CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>if</B><CODE> </CODE>l<CODE>.</CODE>num<CODE> </CODE><CODE>&lt;</CODE><CODE> </CODE>line<CODE>.</CODE>num<CODE> </CODE><B>then</B><CODE> </CODE>l::<TT>(</TT>insert<CODE> </CODE>line<CODE> </CODE>prog<TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE><B>if</B><CODE> </CODE>l<CODE>.</CODE>num<CODE>=</CODE>line<CODE>.</CODE>num<CODE> </CODE><B>then</B><CODE> </CODE>line::prog<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>else</B><CODE> </CODE>line::l::prog<CODE> </CODE>;;<BR><CODE>val insert : line -&gt; line list -&gt; line list = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The <TT>print_prog</TT> function prints the source code of a
program.


<PRE><BR># <B>let</B><CODE> </CODE>print_prog<CODE> </CODE>prog<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>print_line<CODE> </CODE>x<CODE> </CODE><CODE>=</CODE><CODE> </CODE>print_string<CODE> </CODE><TT>(</TT>pp_line<CODE> </CODE>x<TT>)</TT><CODE> </CODE>;<CODE> </CODE>print_newline<CODE> </CODE>()<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_newline<CODE> </CODE>()<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>List.iter<CODE> </CODE>print_line<CODE> </CODE>prog<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_newline<CODE> </CODE>()<CODE> </CODE>;;<BR><CODE>val print_prog : line list -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The <TT>one_command</TT> function processes the insertion of a line
or the execution of a command. It modifies the state of the toplevel
loop, which consists of a program and an environment. This
state, represented by the <I>loop_state</I> type, is different from
the evaluation state.


<PRE><BR># <B>type</B><CODE> </CODE>loop_state<CODE> </CODE><CODE>=</CODE><CODE> </CODE>{<CODE> </CODE>prog<CODE>:</CODE>program;<CODE> </CODE>env<CODE>:</CODE>environment<CODE> </CODE>}<CODE> </CODE>;;<BR># <B>exception</B><CODE> </CODE>End<CODE> </CODE>;;<BR>

</PRE>

<A NAME="fun-une-commande"></A>


<PRE><BR># <B>let</B><CODE> </CODE>one_command<CODE> </CODE>state<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"&gt; "</CODE><CODE> </CODE>;<CODE> </CODE>flush<CODE> </CODE>stdout<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>try</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>parse<CODE> </CODE><TT>(</TT>input_line<CODE> </CODE>stdin<TT>)</TT><CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Line<CODE> </CODE>l<CODE> </CODE>-&gt;<CODE> </CODE>{<CODE> </CODE>state<CODE> </CODE><B>with</B><CODE> </CODE>prog<CODE> </CODE><CODE>=</CODE><CODE> </CODE>insert<CODE> </CODE>l<CODE> </CODE>state<CODE>.</CODE>prog<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>List<CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><TT>(</TT>print_prog<CODE> </CODE>state<CODE>.</CODE>prog<CODE> </CODE>;<CODE> </CODE>state<CODE> </CODE><TT>)</TT><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Run<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>tprog<CODE> </CODE><CODE>=</CODE><CODE> </CODE>assemble<CODE> </CODE>state<CODE>.</CODE>prog<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>xstate<CODE> </CODE><CODE>=</CODE><CODE> </CODE>run<CODE> </CODE>{<CODE> </CODE>line<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>0</CODE>;<CODE> </CODE>xprog<CODE> </CODE><CODE>=</CODE><CODE> </CODE>tprog;<CODE> </CODE>xenv<CODE> </CODE><CODE>=</CODE><CODE> </CODE>state<CODE>.</CODE>env<CODE> </CODE>}<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{state<CODE> </CODE><B>with</B><CODE> </CODE>env<CODE> </CODE><CODE>=</CODE><CODE> </CODE>xstate<CODE>.</CODE>xenv<CODE> </CODE>}<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>PEnd<CODE> </CODE>-&gt;<CODE> </CODE>raise<CODE> </CODE>End<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>LexerError<CODE> </CODE>-&gt;<CODE> </CODE>print_string<CODE> </CODE><CODE>"Illegal character\n"</CODE>;<CODE> </CODE>state<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>ParseError<CODE> </CODE>-&gt;<CODE> </CODE>print_string<CODE> </CODE><CODE>"syntax error\n"</CODE>;<CODE> </CODE>state<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>RunError<CODE> </CODE>n<CODE> </CODE>-&gt;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"runtime error at line "</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_int<CODE> </CODE>n<CODE> </CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"\n"</CODE>;<CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>state<CODE> </CODE>;;<BR><CODE>val one_command : loop_state -&gt; loop_state = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The main function is the <TT>go</TT> function, which starts the
toplevel loop of our Basic.


<PRE><BR># <B>let</B><CODE> </CODE>go<CODE> </CODE>()<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><B>try</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>print_string<CODE> </CODE><CODE>"Mini-BASIC version 0.1\n\n"</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>loop<CODE> </CODE>state<CODE> </CODE><CODE>=</CODE><CODE> </CODE>loop<CODE> </CODE><TT>(</TT>one_command<CODE> </CODE>state<TT>)</TT><CODE> </CODE><CODE> </CODE><B>in</B><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>loop<CODE> </CODE>{<CODE> </CODE>prog<CODE> </CODE><CODE>=</CODE><CODE> </CODE>[];<CODE> </CODE>env<CODE> </CODE><CODE>=</CODE><CODE> </CODE>[]<CODE> </CODE>}<BR><CODE> </CODE><B>with</B><CODE> </CODE>End<CODE> </CODE>-&gt;<CODE> </CODE>print_string<CODE> </CODE><CODE>"See you later...\n"</CODE>;;<BR><CODE>val go : unit -&gt; unit = &lt;fun&gt;</CODE><BR>

</PRE>

The loop is implemented by the local function <TT>loop</TT>. It
stops when the <TT>End</TT> exception is raised by the
<TT>one_command</TT> function.<BR>
<BR>

<H4> Example: C+/C-</H4>
We return to the example of the C+/C- game described in chapter&nbsp;<A HREF="index.html#chap-PI">3</A>,
page&nbsp;<A HREF="book-ora027.html#cpcm">??</A>. Here is the Basic program corresponding to that
Objective CAML program:<BR>
<BR>
<PRE>
10 PRINT "Give the hidden number: "
20 INPUT N
30 PRINT "Give a number: "
40 INPUT R
50 IF R = N THEN 110
60 IF R &lt; N THEN 90
70 PRINT "C-"
80 GOTO 30
90 PRINT "C+"
100 GOTO 30
110 PRINT "CONGRATULATIONS"
</PRE>And here is a sample run of this program.<BR>
<BR>
<PRE>
&gt; RUN
Give the hidden number:
64
Give a number:
88
C-
Give a number:
44
C+
Give a number:
64
CONGRATULATIONS
</PRE><A NAME="toc85"></A>
<H3> Further work</H3>
The Basic we implemented is minimalist. If you want to go further,
the following exercises hint at some possible extensions.<BR>
<BR>
<OL type=1>
<LI> <EM>Floating-point numbers</EM>: as is, our language only deals with
integers, strings and booleans. Add floats, as well as the
corresponding arithmetic operations in the language grammar. We need
to modify not only parsing, but also evaluation, taking into
account the implicit conversions between integers and floats.<BR>
<BR>

<LI> <EM>Arrays</EM>: Add to the syntax the command <TT>DIM
 var[x]</TT> that declares an array <TT>var</TT> of size <TT>x</TT>, and the
 expression <TT>var[i]</TT> that references the <TT>i</TT>th element of the
 array <TT>var</TT>.<BR>
<BR>

<LI> <EM>Toplevel directives</EM>: Add the toplevel directives <TT>SAVE "file_name"</TT> and <TT>LOAD "file_name"</TT> that save a Basic
 program to the hard disk, and load a Basic program from the hard
 disk, respectively.<BR>
<BR>

<LI> <EM>Sub-program</EM>: Add sub-programs. The <TT>GOSUB line
 number</TT> command calls a sub-program by branching to the given
 line number while storing the line from where the call is made. The
 <TT>RETURN</TT> command resumes execution at the line following the
 last <TT>GOSUB</TT> call executed, if there is one, or exits the
 program otherwise. Adding sub-programs requires evaluation to
 manage not only the environement but also a stack containing the
 return addresses of the current <TT>GOSUB</TT> calls. The <TT>GOSUB</TT>
 command adds the possibility of defining recursive sub-programs.
</OL><HR>
<A HREF="book-ora057.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora059.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
